package _18_剑指OfferII;

import java.util.Arrays;

public class _040_剑指OfferII矩阵中最大的矩形 {

    // 使用柱状图加单调栈优化
    // 计算矩阵中最大矩形的面积
    public int maximalRectangle(char[][] matrix) {
        int row = matrix.length;
        if (row == 0) return 0;
        int col = matrix[0].length;
        int results = 0;
        int[][] left =  new int[row][col];
        // 初始化数据
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (matrix[i][j] == '1') {
                    left[i][j] = (j > 0? left[i][j - 1]: 0) + 1;
                }
            }
        }

        for (int i = 0; i < col; ++i) {
            int[] upMin = new int[row];
            Arrays.fill(upMin, -1);
            int[] downMin = upMin.clone();
            for (int j = 1; j < row; ++j) {
                int position = j - 1;
                while (left[position][i] >= left[j][i]) {
                    if (upMin[position] == -1) {
                        position = -1;
                        break;
                    }
                    position = upMin[position];
                }
                upMin[j] = position;
            }

            for (int j = row - 2; j >= 0; --j) {
                int position = j + 1;
                while (left[position][i] >= left[j][i]) {
                    if (downMin[position] == -1) {
                        position = -1;
                        break;
                    }
                    position = downMin[position];
                }
                downMin[j] = position;
            }

            // 计算面积
            for (int j = 0; j < row; j++) {
                int upWidth = upMin[j] == -1? j + 1: j - upMin[j];
                int downWidth = downMin[j] == -1? row - j: downMin[j] - j;
                results = Math.max(results, (upWidth + downWidth - 1) * left[j][i]);
            }

        }
        return results;
    }

    // 使用柱状图优化
    public int maximalRectangle2(char[][] matrix) {
        int row = matrix.length;
        if (row == 0) return 0;
        int col = matrix[0].length;
        int results = 0;
        int[][] left =  new int[row][col];
        // 初始化数据
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (matrix[i][j] == '1') {
                    left[i][j] = (j > 0? left[i][j - 1]: 0) + 1;
                }
            }
        }
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (matrix[i][j] != '0') continue;
                int width = left[i][j];
                int area = width;
                for (int k = i - 1; k >= 0; --k) {
                    width = Math.min(width, left[k][j]);
                    area = Math.max(area, width * (i - k + 1));
                }
                results = Math.max(results, area);
            }
        }
        return results;
    }

    // 分别延展长度，和宽度，取最小值，求得矩形面积
    // 暴力求解
    public int maximalRectangle1(char[][] matrix) {
        int row = matrix.length;
        if (row == 0) return 0;
        int col = matrix[0].length;
        int max = 0;
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (matrix[i][j] == '1') {
                    int tempRow = i;
                    int tempCol = j;
                    // 高度延展
                    while (tempRow < row - 1 && matrix[tempRow + 1][j] == '1')
                        tempRow++;
                    while (tempCol < col - 1 && matrix[i][tempCol + 1] == '1')
                        tempCol++;
                    for (int k = i; k <= tempRow; ++k) {
                        for (int l = j; l <= tempCol; ++l) {
                            if (matrix[k][l] == '1') {
                                max = Math.max((k - i + 1) * (l - j + 1), max);
                            } else {
                                tempCol = l - 1;
                                break;
                            }
                        }
                    }
                }
            }
        }
        return max;
    }

}
